目前主要有三種方法來求解遞迴式(至今沒有任何一個好的演算法可以有效地解決遞迴式)
他主要遵循以下三種想法
Example 1. , Θ
我們先猜測大約
先證明基本情況,Θ ,當c足夠大時,不等式成立。
接下來證明最多達到,我們將這個表示式展開,對成立,這裡不使用Big-O符號作為表示原因在於不能對Big-O符號進行歸納,以下面例子來說:
假設,當n足夠大時,n會小於等於常數1,也就是n不會超出常數時間。如果這個為真,那任何演算法都將會是常數時間複雜度,但顯然這是錯的
基本情況
根據數學歸納法,如果假設
我們可以推出,如果是,1也是
則總和還是,因此由數學歸納法,正確
但這是一個錯誤的證明,問題點是我們忽略了常數的變化可能會使常數加倍,如果是有限情況下,常數不斷加倍仍然是常數,但如果這是一個無窮表示式,常數乘了n倍,那就會出問題了,常數會根據n變化,因此不能被忽略。
為了避免上面這個問題,於是我們將常數寫出來,以k做為表示,對成立,我們將展開,,根據我們上面的歸納假設
(小括弧部分為剩餘項,是為了化簡到)
, 當餘項大於或是等於零時
我們證明一下餘項必定大於或等於零,如果c為2,則必定大於零成立,如果c為1,則,當n大於1點多時,必成立。
到這裡我們證明完畢小於或等於一個常數乘上,這個就是的上界,但其實這不是一個嚴格的上界,因為也同樣會成立。這裡所證明的不是的答案就是,而是不會超過這件事情。
我們試著證明
當
,使用上面歸納法的假設將展開
,(小括號的部分式為餘項)
,我們必須讓餘項非負,因為對於遞迴式來說,只討論大於等於1的情況
寫到這裡我們會發現我們無法完成這個歸納法,因此,我們需要修改我們假設
假設當,這裡我們改進了我們的歸納法假設,我們之前用的假設是與目前相比較弱的假設,在現在這個假設中,我們把低次項加入進來考慮,先前的假設忽略了常數項與低次項。
我們這裡之所以考慮進來低次項,原因是我們期望在解遞迴式的過程,可以把n給消除掉,只留下,下面開始證明
假設 當
,這裡使用了更強的歸納假設,因此需要留下最次低項
中括號部分為餘項,同時我們希望餘項非負
我們發現當時,餘項恆正,因此證明
,當時
接著回頭看到基本情況的部分
Θ
我們會發現到,需要大於等於1,那需要足夠大,才能滿足 Θ,因此整個歸納法的精確結論如下
,當且相對於足夠大時
遞迴樹解法,顧名思義是把遞迴以樹的形式展開,雖然直覺,但是相較於代換法沒有那麼的嚴謹,中間遞迴過程有時候會以...省略,這裡需要特別注意,若要求嚴謹,可以使用代換法去驗證遞迴樹,但一般來說不會那麼做。
Example 1.
首先,我們先將這個遞迴式以樹的形式表達,如下圖
再將和帶入,也就是遞迴展開的概念。
然後一直不斷下去,直到最後,我們會得到一堆葉節點,為Θ。
這裡我們可以注意到一件事情,左子樹和右子樹的遞迴展開速度是不一樣的,會導致兩子樹的高度不同,我們會難以計算葉子的數量,但我們能夠確定一件事情,就是葉子的數量一定會少於n,一開始問題的規模為n,每一次遞迴會減少1/4,因此當遞迴結束於,葉的數量必定會少於n,我們試著把這個樹每一層的結果加總
我們會發現每一層都會相差,我們把加總,也就是求這個等比級數的何
我們知道上面這個公式計算之後,我們會得到某個常數,我們以c為代表,整個等比級數的何為
,且,以Ω表示
而這個方法不嚴謹的地方在於等比級數得假設,我們只驗證了前三項就認定他是等比級數。下面會介紹基於遞迴樹的更嚴謹的方法,稱為主定理(master theorem)。
主定理有一個限制,那就是只能使用到特定的遞迴式上面,這些遞迴式需要符合這樣的形式,有a個相同的子問題,每個子問題的規模皆相同,不同於上一個例題,有兩個不同規模的子問題。
還有一些限制條件,a需要大於或是等於1,也就是至少要遞迴一次,b需要嚴格大於1,因為我們必須讓子問題的規模越來越小,f(n)需要趨近於正(asymptotically positive),也就是當n足夠大時,必須為正,以數學式表示,即為存在某一個點,當時,
主定理是基於將非遞迴函數和進行比較,而比較的過程,會出現三種情況,分別為大於,等於,小於,我們可能會直觀的想到使用little-o,big-Θ,和smail-ω做為表示,但是,中間會存在一些灰色地帶,是我們無法用這些符號進行表示的。
Example 1.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認是屬於哪一種情況,也就是先計算
,將代入,得到
我們比較和,發現,也就是,因此屬於第一種情況,則結果為,也就是
Example 2.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認是屬於哪一種情況,也就是先計算
,將代入,得到
我們比較和,發現,也就是,因此屬於第二種情況,則結果為,也就是
Example 3.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認是屬於哪一種情況,也就是先計算
,將代入,得到
我們比較和,發現,也就是,因此屬於第三種情況,則結果為,也就是
參考資料: Introduciton to algorithms 3rd